from search import *

#Defino el problema a tratar
class Sorting(Problem):
	
    def __init__(self,elems,tipo):
        self.initial = elems
        self.nodos_expandidos = 0
        self.tipo    = tipo # 0= bruteforce, 1= bubble, 2= merge

    def goal_test(self,state):
      res = True
      for i in range(len(state)-1):
        if state[i]>state[i+1]:
            res = False
      return res


    def successor(self, state):
        """El codigo necesita castear varias veces entre list y tuple
           el algoritmo de aima necesita tuples pero yo al modificar los estados
           necesito lists"""

        ret = []

        #bruteforce
        if self.tipo == 0:
           for i in range(len(state)-1):
               temp = list(state)
               temp[i],temp[i+1] = temp[i+1],temp[i]
               ret.append((0,tuple(temp)))

        #bubble
        elif self.tipo == 1:
           for i in range(len(state)-1):
             if state[i]>state[i+1]:
               temp = list(state)
               temp[i],temp[i+1] = temp[i+1],temp[i]
               ret.append((1,tuple(temp)))

        #merge
        elif self.tipo == 2:
           #creo los bloques
           bloqs = []
           i=0
           for j in range(1,len(state)):
             if state[j-1] > state[j]:
               bloqs.append(state[i:j])
               i = j
           bloqs.append(state[i:])

           #mergeo 2 continuos
           for i in range(len(bloqs)-1):
             temp = []

             for j in range(0,i):
               temp += bloqs[j]

             temp += self.merge(bloqs[i],bloqs[i+1])

             for j in range(i+2,len(bloqs)):
               temp += bloqs[j]

             ret.append((2,tuple(temp)))

        self.nodos_expandidos += 1
        return ret
          
    def merge(self,bloqs_i,bloqs_j):
      a = list(bloqs_i)
      b = list(bloqs_j)
      out = []
      while len(a) and len(b):
         if a[0]<=b[0]:
            out.append(a.pop(0))
         else:
            out.append(b.pop(0))

      if len(a)==0:      
         out.extend(b)
      elif len(b)==0:
         out.extend(a)
      return tuple(out)

    def h1(self,node):
       #cant de elems desordenados contiguos (i>i+1)
       #es admisible porque por lo menos se necesitan esa
       #cantidad de swaps para el resultado correcto
       res = 0
       for i in range(len(node.state)-1):
         if node.state[i]>node.state[i+1]:
             res += 1
       return res

    def h2(self,node):
      #para cada elem, cuantos elems mayores tiene
      #me quedo con el mayor
      maximo = 0
      for i in range(1,len(node.state)-1):
       cant = 0
       for j in range(0,i):
         if node.state[i]<node.state[j]:
           cant+=1
       if cant > maximo: maximo = cant
      return maximo


a = Sorting( (4, 6, 14, 0, 5, 8, 15, 7,9,5) ,0)

best_first_graph_search(a,a.h2)
print a.nodos_expandidos
